//给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 
//
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 
//
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 
//
// 
//
// 示例 1： 
//
// 
//输入：k = 2, prices = [2,4,1]
//输出：2
//解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。 
//
// 示例 2： 
//
// 
//输入：k = 2, prices = [3,2,6,5,0,3]
//输出：7
//解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
//     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 
//。 
//
// 
//
// 提示： 
//
// 
// 0 <= k <= 100 
// 0 <= prices.length <= 1000 
// 0 <= prices[i] <= 1000 
// 
// Related Topics 数组 动态规划 
// 👍 626 👎 0

package com.cute.leetcode.editor.cn;
public class BestTimeToBuyAndSellStockIv {
    public static void main(String[] args) {
        Solution solution = new BestTimeToBuyAndSellStockIv().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 将最多两次交易扩成了最多k次交易，按照上一个题目的题解来看的话可以定义如下状态
     * dp[i][j][k]
     * i表示第i天，j表示交易次数，k表示是否持股
     * 初始话的条件和之前类似，不存在且可能用到的值赋值为MIN
     * 每一天更新条件时需要将所有买入次数都进行更新
     * 最后返回dp[len-1][k][0]
     *
     *
     * 空间压缩：可以直接把第一维去掉？？？
     * int[][] dp = new int[k+1][2];
     * for (int i = 0; i <= k; i++) {
     *      dp[i][1] = Integer.MIN_VALUE;
     *  }
     * for (int price : prices) {
     *      for (int j = 1; j <= k; j++) {
     *           p[j][1] = Math.max(dp[j][1], dp[j - 1][0] - price);
     *           dp[j][0] = Math.max(dp[j][0], dp[j][1] + price);
     *        }
     *     }
     *   return dp[k][0];
     */
    class Solution {
        public int maxProfit(int k, int[] prices) {
            int len = prices.length;
            if (len<2 || k==0) return 0;
            //这里可以根据k进行一下优化：如果k>=len/2说明交易次数不受限制，可以任意次数的交易，直接用贪心
            if (k>= len/2)
                return greedy(prices,len);
            int[][][] dp = new int[len][k+1][2];
            // 初始化：把持股的部分都设置为一个较小的负值
            // 注意：如果使用默认值 0，状态转移的过程中会做出错误的决策
            for (int i = 0; i < len; i++) {
                for (int j = 0; j <= k; j++) {
                    dp[i][j][1] = Integer.MIN_VALUE;
                }
            }
            for (int i = 1; i < len ; i++) {
                for (int j = 1; j <=k ; j++) {
                    //当前次数为j且持股：前一天次数为j且持股，前一天次数为j-1，今天买入
                    dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
                    //当前次数为j且不持股：前一天次数为j不持股，前一天次数为j持股且今天卖出
                    dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1] + prices[i]);
                }
            }
            return dp[len-1][k][0];
        }

        /**
         * 贪心求不限交易次数的最大利润，有利润就交易
         */
        private int greedy(int[] prices,int len) {
            int res = 0;
            for (int i = 1; i < len; i++)
                if (prices[i]>prices[i-1]) res += prices[i]- prices[i-1];
            return res;
        }

        /**
         * 二刷的时候看到代码随想录受到的启发，一共k次交易的话一天的状态有2*k+1种
         * 所以可以对2*k种状态分别进行推导 1：第一次买入，2：第一次卖出；3：第二次买入，4：第二次卖出；....
         * 同时使用cur和pre两个数组压缩空间
         * 时间复杂度为n*k，空间复杂度为k
         */
        public int maxProfit2(int k, int[] prices) {
            int len = prices.length;
            if (len == 0) return 0;
            int[] pre = new int[2*k+1];
            int[] cur = new int[2*k+1];
            for (int i = 1; i < 2*k; i += 2) pre[i] = -prices[0];
            for (int i = 1; i<len; i++){
                for (int j = 1; j < 2*k; j+=2){
                    //当前买入只能从两个状态推过来
                    cur[j] = Math.max(pre[j],pre[j-1] - prices[i]);
                    //当前卖出只能从两个状态推过来
                    cur[j+1] = Math.max(pre[j+1],pre[j] + prices[i]);
                }
                pre = cur;
            }
            return cur[2*k];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}